package com.zjw.algorithm;


import com.zjw.algorithm.utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 给出二叉树的根节点 root，树上每个节点都有一个不同的值。
 * <p>
 * 如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。
 * <p>
 * 返回森林中的每棵树。你可以按任意顺序组织答案。
 * <p>
 *  
 * <p>
 * 示例 1：
 * 1
 * 2    3
 * 4 5    6 7
 * <p>
 * <p>
 * 输入：root = [1,2,3,4,5,6,7], to_delete = [3,5]
 * 输出：[[1,2,null,4],[6],[7]]
 * 示例 2：
 * <p>
 * 输入：root = [1,2,4,null,3], to_delete = [3]
 * 输出：[[1,2,4]]
 *  
 * <p>
 * 提示：
 * <p>
 * 树中的节点数最大为 1000。
 * 每个节点都有一个介于 1 到 1000 之间的值，且各不相同。
 * to_delete.length <= 1000
 * to_delete 包含一些从 1 到 1000、各不相同的值。
 * 通过次数35,945提交次数51,834
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/delete-nodes-and-return-forest
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Solution3 {
    /**
     * DFS解决
     */
    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        List<TreeNode> result = new ArrayList<>();
        delNodesImpl(root, null, true, to_delete, result);
        return result;
    }

    private void delNodesImpl(TreeNode root, TreeNode parent, boolean isLeft, int[] toDelete, List<TreeNode> result) {
        if (root == null) {
            return;
        }

        if (parent == null) {
            if (containItem(toDelete, root.val)) {
                delNodesImpl(root.left, null, true, toDelete, result);
                delNodesImpl(root.right, null, false, toDelete, result);
            } else {
                result.add(root);
                delNodesImpl(root.left, root, true, toDelete, result);
                delNodesImpl(root.right, root, false, toDelete, result);
            }
        } else {
            if (containItem(toDelete, root.val)) {
                if (isLeft) {
                    parent.left = null;
                } else {
                    parent.right = null;
                }
                delNodesImpl(root.left, null, true, toDelete, result);
                delNodesImpl(root.right, null, false, toDelete, result);
            } else {
                delNodesImpl(root.left, root, true, toDelete, result);
                delNodesImpl(root.right, root, false, toDelete, result);
            }
        }
    }


    private boolean containItem(int[] arr, int item) {
        for (int j : arr) {
            if (j == item) {
                return true;
            }
        }
        return false;
    }

}
